package algorithm.leetcode;

import algorithm.templates.Node;

import java.util.HashMap;
import java.util.Map;

public class NO138_随机链表的复制 {

    static class OfficialSolution {
        public Node copyRandomList(Node head) {
            if (head == null) {
                return null;
            }
            Node cur = head;
            Map<Node, Node> mappingNodes = new HashMap<>();
            while (cur != null) {
                Node newNode = new Node(cur.val);
                mappingNodes.put(cur, newNode);
                cur = cur.next;
            }
            cur = head;
            while (cur != null) {
                Node copiedNode = mappingNodes.get(cur);
                copiedNode.next = mappingNodes.get(cur.next);
                copiedNode.random = mappingNodes.get(cur.random);
                cur = cur.next;
            }
            return mappingNodes.get(head);
        }
    }

    static class Solution {
        public Node copyRandomList(Node head) {
            if (head == null) {
                return null;
            }

            Node temp = head;
            Map<Node, Node> interweave = new HashMap<>();

            while (temp != null) {
                interweave.put(temp, temp.random);
                temp = temp.next;
            }

            Node start = null, result = null;
            int flag = 0;
            while (head != null) {
                start = new Node(head.val);
                if (flag == 0) {
                    result = start;
                    flag = 1;
                }

                start.next = head.next;
                start.random = interweave.get(head);

                head = head.next;
            }

            return result;
        }
    }
}
